{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Win From Two Segments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximizeWin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个线段获得的最多奖品"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在 <strong>X轴</strong>&nbsp;上有一些奖品。给你一个整数数组&nbsp;<code>prizePositions</code>&nbsp;，它按照 <strong>非递减</strong>&nbsp;顺序排列，其中&nbsp;<code>prizePositions[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以选择两个端点为整数的线段。每个线段的长度都必须是 <code>k</code>&nbsp;。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说&nbsp;<code>k = 2</code>&nbsp;，你可以选择线段&nbsp;<code>[1, 3]</code> 和&nbsp;<code>[2, 4]</code>&nbsp;，你可以获得满足&nbsp;<code>1 &lt;= prizePositions[i] &lt;= 3</code> 或者&nbsp;<code>2 &lt;= prizePositions[i] &lt;= 4</code>&nbsp;的所有奖品 i 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回在选择两个最优线段的前提下，可以获得的 <strong>最多</strong>&nbsp;奖品数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>prizePositions = [1,1,2,2,3,3,5], k = 2\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>这个例子中，你可以选择线段 [1, 3] 和 [3, 5] ，获得 7 个奖品。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>prizePositions = [1,2,3,4], k = 0\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>这个例子中，一个选择是选择线段 <code>[3, 3]</code> 和 <code>[4, 4] ，获得 2 个奖品。</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= prizePositions.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= prizePositions[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>9</sup> </code></li>\n",
    "\t<li><code>prizePositions</code>&nbsp;有序非递减。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-win-from-two-segments](https://leetcode.cn/problems/maximize-win-from-two-segments/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-win-from-two-segments](https://leetcode.cn/problems/maximize-win-from-two-segments/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2,2,3,3,5]\\n2', '[1,2,3,4]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        pre = [0] * (n + 1)\n",
    "        ans = left = 0\n",
    "\n",
    "        for right, pos in enumerate(prizePositions):\n",
    "            while left < n and prizePositions[left] < prizePositions[right] - k:\n",
    "                left += 1\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "            if right - left + 1 + pre[left] > ans:\n",
    "                ans = right - left + 1 + pre[left]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        if len(prizePositions)==1:\n",
    "            return 1\n",
    "        sumright = [0 for _ in range(len(prizePositions))]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        cnt = 0\n",
    "        while i <len(prizePositions):\n",
    "            cnt += 1\n",
    "            while j <=i and prizePositions[i]- prizePositions[j]>k:\n",
    "                cnt -= 1\n",
    "                j += 1\n",
    "            sumright[i] = cnt\n",
    "            i+=1\n",
    "        for i in range(1,len(prizePositions)):\n",
    "            sumright[i] = max(sumright[i-1],sumright[i])\n",
    "        #print(sumright)\n",
    "        i = len(prizePositions)-1\n",
    "        j = i\n",
    "        cnt = 0\n",
    "        summ = 0\n",
    "        while i >0:\n",
    "            while j > i and prizePositions[j]-prizePositions[i] > k:\n",
    "                j -= 1\n",
    "            summ = max(summ,sumright[i-1]+j-i+1)\n",
    "            #print(summ,sumright[i-1],j-i+1,i,j)\n",
    "            i -= 1\n",
    "        #print(sumright[0])\n",
    "        return summ\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        mxs = [0] * (n + 1)\n",
    "        ans = mx = 0\n",
    "        i = n - 1\n",
    "        while i > -1:\n",
    "            while i - 1 > -1 and prizePositions[i - 1] == prizePositions[i]:\n",
    "                i -= 1\n",
    "            j = bisect_right(prizePositions, prizePositions[i] + k)\n",
    "            ans = max(ans, j - i + mxs[j])\n",
    "            mx = max(mx, j - i)\n",
    "            mxs[i] = mx\n",
    "            i -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        left,ans = 0,0\n",
    "        pre = [0] * (n+1)\n",
    "        for right in range(n):\n",
    "            while prizePositions[right] - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            pre[right+1] = max(pre[right],right - left + 1)\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        if prizePositions[-1] - prizePositions[0] <= 2*k:\n",
    "            return len(prizePositions)\n",
    "        left = 0\n",
    "        pre = [0 for _ in range(len(prizePositions) + 1)]\n",
    "        res = 0\n",
    "        for right in range(len(prizePositions)):\n",
    "            while prizePositions[right] - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            res = max(res,pre[left]+ right - left + 1)\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        pre = [0] * n\n",
    "        ans = left = 0\n",
    "        for right, pos in enumerate(prizePositions):\n",
    "            #print(left, right, pre)\n",
    "            while pos - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            #print(left, right, pre)\n",
    "            ans = max(ans, right - left + 1 + pre[left - 1])\n",
    "            pre[right] = max(pre[right - 1], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, nums: List[int], k: int) -> int:\n",
    "        # 两个线段不重叠最优\n",
    "        # 枚举第二个线段的左端点l, 那么为题变成了在[0 : l - 1]内找到最优的左线段\n",
    "        n = len(nums)\n",
    "        f = [0] * n # 存右端点为r的最多奖品数量f[r]\n",
    "        l, now = 0, 0\n",
    "        for r in range(n):\n",
    "            now += 1\n",
    "            # 最大滑窗\n",
    "            while l <= r and nums[r] - nums[l] > k:\n",
    "                l += 1\n",
    "                now -= 1\n",
    "            f[r] = now\n",
    "        # f 变为前缀最大数组, 存右端点不超过i的线段多奖品\n",
    "        for i in range(1, n, +1):\n",
    "            f[i] = max(f[i - 1], f[i])\n",
    "        # 枚举右边线段的左端点\n",
    "        r = n - 1\n",
    "        now = 0\n",
    "        ans = 0\n",
    "        for l in range(n - 1, -1, -1):\n",
    "            now += 1\n",
    "            while l <= r and nums[r] - nums[l] > k:\n",
    "                now -= 1\n",
    "                r -= 1\n",
    "            ans = max(ans, now + (f[l - 1] if l > 0 else 0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        f = [0] * (n + 1)\n",
    "        res = l = 0\n",
    "\n",
    "        for r, pos in enumerate(prizePositions):\n",
    "            while pos - prizePositions[l] > k:\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1 + f[l])\n",
    "            f[r + 1] = max(f[r], r - l + 1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        if len(prizePositions)==1:\n",
    "            return 1\n",
    "        sumright = [0 for _ in range(len(prizePositions))]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        cnt = 0\n",
    "        while i <len(prizePositions):\n",
    "            cnt += 1\n",
    "            while j <=i and prizePositions[i]- prizePositions[j]>k:\n",
    "                cnt -= 1\n",
    "                j += 1\n",
    "            sumright[i] = cnt\n",
    "            i+=1\n",
    "        for i in range(1,len(prizePositions)):\n",
    "            sumright[i] = max(sumright[i-1],sumright[i])\n",
    "        #print(sumright)\n",
    "        i = len(prizePositions)-1\n",
    "        j = i\n",
    "        cnt = 0\n",
    "        summ = 0\n",
    "        while i >0:\n",
    "            while j > i and prizePositions[j]-prizePositions[i] > k:\n",
    "                j -= 1\n",
    "            summ = max(summ,sumright[i-1]+j-i+1)\n",
    "            print(summ,sumright[i-1],j-i+1,i,j)\n",
    "            i -= 1\n",
    "        #print(sumright[0])\n",
    "        return summ\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        total = len(prizePositions)\n",
    "        pre_max = 0\n",
    "        l, r = 0, 0\n",
    "        ret = 0\n",
    "        for m in range(total):\n",
    "            while r < total and prizePositions[r] - prizePositions[m] <= k:\n",
    "                r += 1\n",
    "            ret = max(ret, pre_max + r-m)\n",
    "            while l < m and prizePositions[m] - prizePositions[l] > k:\n",
    "                l += 1\n",
    "            pre_max = max(pre_max, m-l+1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int: \n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        l = ans = 0\n",
    "\n",
    "        for r, v in enumerate(prizePositions):\n",
    "            while prizePositions[r] - prizePositions[l] > k:\n",
    "                l += 1\n",
    "            \n",
    "            cur_len = r - l + 1\n",
    "            ans = max(ans, cur_len + pre[l])\n",
    "            pre[r + 1] = max(pre[r], cur_len)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        pre = [0] * (n + 1)\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for right in range(n):\n",
    "            while prizePositions[right] - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        res = 0\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        for right, pos in enumerate(prizePositions):\n",
    "            while pos - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1 + pre[left])\n",
    "            pre[right+1] = max(pre[right], right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        prizePositions.sort()\n",
    "        prev = [0] * (len(prizePositions)+1)\n",
    "        res = 0\n",
    "        idx = 0\n",
    "        for j in range(len(prizePositions)):\n",
    "            while prizePositions[j] - prizePositions[idx] > k:\n",
    "                idx += 1\n",
    "            value = (j-idx+1) + prev[idx]\n",
    "            #print(f'{idx=} {j=} {value=}, {prev=}')\n",
    "            res = max(res, value)\n",
    "            prev[j+1] = max(j-idx+1, prev[j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        r=0\n",
    "        n=len(prizePositions)\n",
    "        # next[i]记录比prizePositions[i]大k的最小下标,next[i]-i即可表示以i位置为起点，单线段能获得的最大礼物量\n",
    "        next=[0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            while r<n and prizePositions[r]-prizePositions[i]<=k:\n",
    "                r+=1\n",
    "            next[i]=r\n",
    "        # postfix记录以i或任意大于i位置为起点，单线段所能获得的最大礼物量\n",
    "        postfix=[0 for _ in range(n+1)]\n",
    "        # postfix[-2]=1\n",
    "        for i in reversed(range(n)):\n",
    "            postfix[i]=max(next[i]-i,postfix[i+1])\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans=max(ans,next[i]-i+postfix[next[i]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        r=0\n",
    "        n=len(prizePositions)\n",
    "        # next[i]记录比prizePositions[i]大k的最小下标,如果不存在，则值为n,next[i]-i即可表示以i位置为起点，单线段能获得的最大礼物量\n",
    "        next=[0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            while r<n and prizePositions[r]-prizePositions[i]<=k:\n",
    "                r+=1\n",
    "            next[i]=r\n",
    "        # postfix记录以i或任意大于i位置为起点，单线段所能获得的最大礼物量，由于next[i]最大可能为n，所以数组长度设置为n+1\n",
    "        postfix=[0 for _ in range(n+1)]\n",
    "        # postfix[-1]设置为0不要动，因为当第一个线段涵盖了最后一个数时，在其后的第二个线段无法得到礼物\n",
    "        for i in reversed(range(n)):\n",
    "            postfix[i]=max(next[i]-i,postfix[i+1])\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans=max(ans,next[i]-i+postfix[next[i]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        # 最多奖品个数 = 双指针区间长度最大值\n",
    "        # 线段长度必须是k：只需要prizePositions[right]-prizePositions[left]<=k即可\n",
    "        n = len(prizePositions)\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        res = [0]*n # res[i]表示前i个奖品中选择的最大奖品数\n",
    "        for right in range(n):\n",
    "            while prizePositions[right]-prizePositions[left]>k:\n",
    "                left+=1\n",
    "            # 当前区间全选，并且加上前left-1个奖品中的最佳选择\n",
    "            ans = max(ans,right-left+1 + (res[left-1] if left else 0))\n",
    "            res[right] = max(res[right-1],right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        pre = [0] * (n + 1)\n",
    "        ans = left = 0\n",
    "\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "\n",
    "        pre = [0] * n\n",
    "        pre_max = [0] * (n + 1)\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        for j in range(n):\n",
    "            while prizePositions[j] - prizePositions[i] > k:\n",
    "                i += 1\n",
    "            pre[j] = j - i + 1\n",
    "            cur = pre[j] + pre_max[i]\n",
    "            if cur > ans:\n",
    "                ans = cur\n",
    "            pre_max[j + 1] = max(pre_max[j], pre[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prize: List[int], k: int) -> int:\n",
    "        n=len(prize)\n",
    "        # if k==0:\n",
    "        #     return min(2,n)\n",
    "        \n",
    "        ans=0\n",
    "        \n",
    "        l=[]\n",
    "        \n",
    "        maxx=[0]*n\n",
    "        \n",
    "        for i in range(n):\n",
    "            index=bisect_left(l,prize[i]-k)\n",
    "            temp1=len(l)-index+1\n",
    "            \n",
    "            \n",
    "            maxx[i]=max(maxx[i-1],temp1)\n",
    "            \n",
    "            ans=max(ans,temp1+(maxx[index-1] if index else 0))\n",
    "            l.append(prize[i])\n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        cnts = sorted([(p, cnt) for p, cnt in Counter(prizePositions).items()])\n",
    "        pres = [0] * (len(cnts)+1)\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        presum = 0\n",
    "        for r,(p, cnt) in enumerate(cnts):\n",
    "            presum += cnt\n",
    "            while p - cnts[l][0] > k:\n",
    "                presum -= cnts[l][1]\n",
    "                l += 1\n",
    "            ans = max(ans, presum + pres[l])\n",
    "            pres[r+1] = max(pres[r], presum)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        lenp = len(prizePositions)\n",
    "        prizePositions.append(float('inf'))\n",
    "        maxPrize = [1] * lenp\n",
    "        left = 0\n",
    "        right = 0\n",
    "        while left < lenp - 1:\n",
    "            if prizePositions[right] <= prizePositions[left] + k:\n",
    "                right += 1\n",
    "                maxPrize[left] = right - left\n",
    "            else:\n",
    "                left += 1\n",
    "                maxPrize[left] = max(1, maxPrize[left - 1] - 1)\n",
    "        ans = 0\n",
    "        maxRight = maxPrize[:]\n",
    "        for i in range(lenp - 2, -1,-1):\n",
    "            if maxRight[i] < maxRight[i + 1]:\n",
    "                maxRight[i] = maxRight[i + 1]\n",
    "        for i in range(lenp):\n",
    "            mx = maxPrize[i]\n",
    "            if i + mx < lenp:\n",
    "                mx += maxRight[i + mx]\n",
    "            if mx > ans:\n",
    "                ans = mx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        pre = [0]*(len(prizePositions)+1)\n",
    "        for right,pr in enumerate(prizePositions):\n",
    "            while pr - prizePositions[left] >k:\n",
    "                left += 1\n",
    "            # if pr - prizePositions[left] == k:\n",
    "            res = max(res, right-left+1 + pre[left])\n",
    "            pre[right+1] = max(pre[right], right-left+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - k > prizePositions[left]:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right+1] = max(pre[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        total = len(prizePositions)\n",
    "        pre_max = 0\n",
    "        l, r = 0, 0\n",
    "        ret = 0\n",
    "        for m in range(total):\n",
    "            while r < total and prizePositions[r] - prizePositions[m] <= k:\n",
    "                r += 1\n",
    "            ret = max(ret, pre_max + r-m)\n",
    "            while l < m and prizePositions[m] - prizePositions[l] > k:\n",
    "                l += 1\n",
    "            pre_max = max(pre_max, m-l+1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        prizePositions.sort()\n",
    "        prev = [0] * (len(prizePositions)+1)\n",
    "        res = 0\n",
    "        for j in range(len(prizePositions)):\n",
    "            idx = bisect_left(prizePositions, prizePositions[j]-k)\n",
    "            value = (j-idx+1) + prev[idx]\n",
    "            #print(f'{idx=} {j=} {value=}, {prev=}')\n",
    "            res = max(res, value)\n",
    "            prev[j+1] = max(j-idx+1, prev[j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, pos: List[int], k: int) -> int:\n",
    "        '''\n",
    "        先转换成区间长度，这样比较好求\n",
    "        双指针，当第二条线段右端点在right的时候，去看左端点最远能在哪里\n",
    "        还需要知道在pos[i]以及pos[i]左侧，最多能够覆盖的区间长度\n",
    "        用pre[i]表示\n",
    "        '''\n",
    "        left=0\n",
    "        ans=0\n",
    "        pre=[0]*(len(pos)+1)\n",
    "        for right,x in enumerate(pos):\n",
    "            while pos[left]<x-k:\n",
    "                left+=1\n",
    "            pre[right+1]=max(pre[right],right-left+1)\n",
    "            ans=max(ans,pre[left]+right-left+1)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, pos: List[int], k: int) -> int:\n",
    "        n = len(pos)\n",
    "        left = ans = 0\n",
    "        pre = [0] * (n+1)\n",
    "        for right,p in enumerate(pos):\n",
    "            while left < right and pos[right] - pos[left] > k:\n",
    "                left+=1\n",
    "            ans = max(ans,right - left+1 + pre[left])\n",
    "            pre[right+1] = max(pre[right], right-left+1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)  # 动态规划数组\n",
    "        ans = 0  # 存储最终答案\n",
    "        left = 0  # 双指针算法中的左指针\n",
    "        \n",
    "        for right, p in enumerate(prizePositions):\n",
    "            # 更新左指针，确保 right - left + 1 内的所有奖品都在长度为 k 的线段内\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            # 更新答案\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            # 更新动态规划数组\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        # 枚举第二条线段的右端点，看第一条线段最多可以覆盖多少个点，\n",
    "        # 先解决一条线段问题\n",
    "\n",
    "        # 强制让第二条线段的右端点恰好落在奖品上，设第二条线段右端点在 prizePositions[right] 时，左端点最远覆盖了 prizePositions[left]，我们需要知道在 prizePositions[left]左侧的第一条线段最多可以覆盖多少个奖品。\n",
    "\n",
    "        #类似两数之和\n",
    "        n = len(prizePositions)\n",
    "        pre = [0]*(n+1) #类似前缀和、哈希，存储left前面的最大值\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for right,p in enumerate(prizePositions):\n",
    "            \n",
    "            #left + 1\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "\n",
    "            ans = max(ans, right -left +1+pre[left]) #right 是算在内的\n",
    "\n",
    "            pre[right + 1] = max(pre[right],right -left +1 )\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        # 最多奖品个数 = 双指针区间长度最大值\n",
    "        # 线段长度必须是k：只需要prizePositions[right]-prizePositions[left]<=k即可\n",
    "        n = len(prizePositions)\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        res = [0]*n\n",
    "        for right in range(n):\n",
    "            while prizePositions[right]-prizePositions[left]>k:\n",
    "                left+=1\n",
    "            ans = max(ans,right-left+1 + (res[left-1] if left else 0))\n",
    "            res[right] = max(res[right-1],right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n=len(prizePositions)\n",
    "        presum=[0]*(n+1)\n",
    "        l=sum=res=0\n",
    "        for r in range(n):\n",
    "            \n",
    "            while(prizePositions[r]-prizePositions[l]>k): l+=1\n",
    "            cur=r-l+1\n",
    "            res=max(res,cur+presum[l])\n",
    "            presum[r+1]=max(cur,presum[r])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        lenp = len(prizePositions)\n",
    "        prizePositions.append(float('inf'))\n",
    "        maxPrize = [1] * lenp\n",
    "        left = 0\n",
    "        right = 0\n",
    "        while left < lenp - 1:\n",
    "            if prizePositions[right] <= prizePositions[left] + k:\n",
    "                right += 1\n",
    "                maxPrize[left] = right - left\n",
    "            else:\n",
    "                left += 1\n",
    "                maxPrize[left] = max(1, maxPrize[left - 1] - 1)\n",
    "        ans = 0\n",
    "        maxRight = maxPrize[:]\n",
    "        for i in range(lenp - 2, -1,-1):\n",
    "            if maxRight[i] < maxRight[i + 1]:\n",
    "                maxRight[i] = maxRight[i + 1]\n",
    "        for i in range(lenp):\n",
    "            mx = maxPrize[i]\n",
    "            if i + mx < lenp:\n",
    "                mx += maxRight[i + mx]\n",
    "            if mx > ans:\n",
    "                ans = mx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(prizePositions)\n",
    "        left = right = ans = 0\n",
    "        pre = [0]*(n+1)\n",
    "\n",
    "        while right<n:\n",
    "            x = prizePositions[right]\n",
    "            while x - prizePositions[left] >k:#值就是索引\n",
    "                left += 1\n",
    "            SumSec = right -left+1\n",
    "            ans = max(ans,pre[left]+SumSec)\n",
    "            pre[right+1] = max(pre[right],SumSec)#这里比较的right,right+1\n",
    "            right += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 枚举第二条线段的右端点，看第一条线段最多可以覆盖多少个点，\n",
    "        # 先解决一条线段问题\n",
    "\n",
    "        # 强制让第二条线段的右端点恰好落在奖品上，设第二条线段右端点在 prizePositions[right] 时，左端点最远覆盖了 prizePositions[left]，我们需要知道在 prizePositions[left]左侧的第一条线段最多可以覆盖多少个奖品。\n",
    "\n",
    "        #类似两数之和\n",
    "        n = len(prizePositions)\n",
    "        pre = [0]*(n+1) #类似前缀和、哈希，存储left前面的最大值\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for right,p in enumerate(prizePositions):\n",
    "            \n",
    "            #left + 1\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "\n",
    "            ans = max(ans, right -left +1+pre[left]) #right 是算在内的\n",
    "\n",
    "            pre[right + 1] = max(pre[right],right -left +1 )\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, p: List[int], k: int) -> int:\n",
    "        n=len(p)\n",
    "        q=[0]*(n+1)\n",
    "        j=0\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            while p[i]-p[j]>k:\n",
    "                j+=1\n",
    "            ans=max(ans,i-j+1+q[j])\n",
    "            q[i+1]=max(q[i],i-j+1)\n",
    "        return ans         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        left = ans = 0\n",
    "        f = [0] * (n+1)\n",
    "        for right, num in enumerate(prizePositions):\n",
    "            while num - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + f[left])\n",
    "            f[right+1] = max(f[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        pre = [0] * (n + 1)\n",
    "        for right in range(n):\n",
    "            while prizePositions[right] - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "        return ans            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        size=len(prizePositions)\n",
    "        l,ans=0,0\n",
    "        pre=[0 for _ in range(len(prizePositions))]\n",
    "        for r in range(size):\n",
    "            while prizePositions[r]-prizePositions[l]>k:\n",
    "                l+=1\n",
    "            ans=max(ans,r-l+1+pre[l-1]) #lr[];pre[]\n",
    "            pre[r]=max(pre[r-1],r-l+1) #记录下标不超过r时，最多可覆盖多少礼品\n",
    "        print(pre)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre = [0] * (len(prizePositions) + 1)\n",
    "        ans = left = 0\n",
    "        for right, p in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + pre[left])\n",
    "            pre[right + 1] = max(pre[right], right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        if prizePositions[-1] - prizePositions[0] <= k*2+1:\n",
    "            return len(prizePositions)\n",
    "        cnts = [[prizePositions[0],0]]\n",
    "        for p in prizePositions:\n",
    "            if p == cnts[-1][0]:\n",
    "                cnts[-1][1] += 1\n",
    "            else:\n",
    "                cnts.append([p, 1])\n",
    "        pres = [0] * (len(cnts)+1)\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        presum = 0\n",
    "        for r,(p, cnt) in enumerate(cnts):\n",
    "            presum += cnt\n",
    "            while p - cnts[l][0] > k:\n",
    "                presum -= cnts[l][1]\n",
    "                l += 1\n",
    "            ans = max(ans, presum + pres[l])\n",
    "            pres[r+1] = max(pres[r], presum)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        #copy 0x3\n",
    "        pre = [0]*(len(prizePositions)+1)\n",
    "        ans = left = 0\n",
    "        for right,p  in enumerate(prizePositions):\n",
    "            while p - prizePositions[left] >k:\n",
    "                left += 1\n",
    "            ans = max(ans,right-left+1+pre[left])\n",
    "            pre[right+1]= max(pre[right],right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        if prizePositions[-1] - prizePositions[0] <= k*2+1:\n",
    "            return len(prizePositions)\n",
    "        cnts = sorted([(p, cnt) for p, cnt in Counter(prizePositions).items()])\n",
    "        pres = [0] * (len(cnts)+1)\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        presum = 0\n",
    "        for r,(p, cnt) in enumerate(cnts):\n",
    "            presum += cnt\n",
    "            while p - cnts[l][0] > k:\n",
    "                presum -= cnts[l][1]\n",
    "                l += 1\n",
    "            ans = max(ans, presum + pres[l])\n",
    "            pres[r+1] = max(pres[r], presum)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, positions: List[int], k: int) -> int:\n",
    "        n = len(positions)\n",
    "        premax = [0] * (n + 1)\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for right, pos in enumerate(positions):\n",
    "            while left <= right and pos - positions[left] > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1 + premax[left])\n",
    "            premax[right + 1] = max(premax[right], right - left + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        l = len(prizePositions)\n",
    "\n",
    "        if prizePositions[0] + k >= prizePositions[-1]:\n",
    "            return l\n",
    "\n",
    "        dp = [0 for _ in range(l)]\n",
    "        preSum = [0 for _ in range(l)]\n",
    "        endIndexes = [0 for _ in range(l)]\n",
    "\n",
    "        startPos = prizePositions[0]\n",
    "        endPos = startPos + k\n",
    "        endIndex = -1\n",
    "        cnt = 0\n",
    "\n",
    "        preSum[0] = 1\n",
    "        for i in range(1, l):\n",
    "            if prizePositions[i] == prizePositions[i - 1]:\n",
    "                preSum[i] = preSum[i - 1] + 1\n",
    "            else:\n",
    "                preSum[i] = 1\n",
    "\n",
    "        for i in range(l):\n",
    "            if prizePositions[i] <= endPos:\n",
    "                cnt += 1\n",
    "                endIndex = i\n",
    "                endIndexes[0] = endIndex\n",
    "            else:\n",
    "                dp[0] = cnt\n",
    "                break\n",
    "\n",
    "        for i in range(1, l):\n",
    "            if prizePositions[i] == prizePositions[i - 1]:\n",
    "                dp[i] = dp[i - 1]\n",
    "                endIndexes[i] = endIndexes[i - 1]\n",
    "            else:\n",
    "                endPos = prizePositions[i] + k\n",
    "                cnt = 0\n",
    "                endIndex = i\n",
    "                while endIndex < l and prizePositions[endIndex] <= endPos:\n",
    "                    endIndex += 1\n",
    "                    cnt += 1\n",
    "                endIndexes[i] = endIndex - 1\n",
    "                dp[i] = endIndex - i\n",
    "\n",
    "        dp2 = dp.copy()\n",
    "        maxx = dp[l - 1]\n",
    "        for i in range(l - 1, -1, -1):\n",
    "            maxx = max(maxx, dp[i])\n",
    "            dp2[i] = maxx\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(l):\n",
    "            if endIndexes[i] + 1 < l:\n",
    "                res = max(res, dp[i] + dp2[endIndexes[i] + 1])\n",
    "            else:\n",
    "                res = max(res, dp[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        counter = Counter(prizePositions)\n",
    "        prize = sorted(counter.items())\n",
    "        n = len(prize)\n",
    "        right = [0] * n  # 从prize[i][0]开始向右长度为k的线段上的奖品数量\n",
    "        r = 0\n",
    "        cur = 0\n",
    "        left = [0] * n # 记录 <= prize[r][0] 线段长度为k的奖品最大数量\n",
    "        ans = 0\n",
    "        for l in range(n):\n",
    "            if l > 0:\n",
    "                cur -= prize[l - 1][1]\n",
    "            while r < n and prize[r][0] - prize[l][0] <= k:\n",
    "                cur += prize[r][1]\n",
    "                if r > 0:\n",
    "                    left[r] = max(left[r - 1], cur)\n",
    "                else:\n",
    "                    left[r] = cur\n",
    "                r += 1\n",
    "            right[l] = cur\n",
    "            if l > 0:\n",
    "                ans = max(ans, right[l] + left[l - 1])\n",
    "            else:\n",
    "                ans = right[l]\n",
    "        # print(prize)\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        if len(prizePositions)==1:\n",
    "            return 1\n",
    "        sumright = [0 for _ in range(len(prizePositions))]\n",
    "        i = 0\n",
    "        j = 0\n",
    "\n",
    "        while i <len(prizePositions):\n",
    "\n",
    "            while j <=i and prizePositions[i]- prizePositions[j]>k:\n",
    "                j += 1\n",
    "            sumright[i] = i-j+1\n",
    "            i+=1\n",
    "        print(sumright)\n",
    "        for i in range(1,len(prizePositions)):\n",
    "            sumright[i] = max(sumright[i-1],sumright[i])\n",
    "        #print(sumright)\n",
    "        i = len(prizePositions)-1\n",
    "        j = i\n",
    "        summ = 0\n",
    "        while i >0:\n",
    "            while j > i and prizePositions[j]-prizePositions[i] > k:\n",
    "                j -= 1\n",
    "            summ = max(summ,sumright[i-1]+j-i+1)\n",
    "            #print(summ,sumright[i-1],j-i+1,i,j)\n",
    "            i -= 1\n",
    "        #print(sumright[0])\n",
    "        return summ\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        q1, q2 = deque(), deque()\n",
    "        k2 = k<<1\n",
    "        sum2 = sum1 = res = 0\n",
    "        max1 = lastM1 = 0\n",
    "        for p, grp in groupby(prizePositions):\n",
    "            n = sum(1 for _ in grp)\n",
    "            while q2 and q2[0][0] <= p - k*2 - 1:\n",
    "                sum2 -= q2.popleft()[1]\n",
    "            while q1 and q1[0][0] <= p - k - 1:\n",
    "                _, n1, lastM1 = q1.popleft()\n",
    "                sum1 -= n1\n",
    "            sum1 += n\n",
    "            sum2 += n\n",
    "            max1 = max(max1, sum1)\n",
    "            q2.append((p, n))\n",
    "            q1.append([p, n, max1])\n",
    "            res = max(res, sum2, lastM1 + sum1)\n",
    "        return res\n",
    "        # M[n] = max(M[n-1,  (M[n-k] + P[n-k+1...n]), P[n-2k+1..n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        pre=[0]*(len(prizePositions)+1)\n",
    "        ans=left=0\n",
    "        for right in range(len(prizePositions)):\n",
    "            while prizePositions[right]-prizePositions[left]>k:\n",
    "                left+=1\n",
    "            ans=max(ans,right-left+1+pre[left])\n",
    "            pre[right+1]=max(pre[right],right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        cnt=Counter(prizePositions)\n",
    "        ls=list(cnt.items())\n",
    "        ls.sort(key=lambda i:i[0])\n",
    "        n=len(ls)\n",
    "        index=0\n",
    "        prels=[0 for i in range(n)]\n",
    "        cur=0\n",
    "\n",
    "        for i in range(n):\n",
    "            while ls[i][0]-ls[index][0]>k:\n",
    "                cur -=ls[index][1]\n",
    "                index+=1\n",
    "            cur+=ls[i][1]\n",
    "            prels[i]=max(prels[i-1],cur)\n",
    "        #print(prels)\n",
    "        index=n-1\n",
    "        cur=0\n",
    "        subls=[0 for i in range(n+1)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while ls[index][0]-ls[i][0]>k:\n",
    "                cur -=ls[index][1]\n",
    "                index-=1\n",
    "            cur+=ls[i][1]\n",
    "            subls[i]=max(subls[i+1],cur)\n",
    "        #print(subls)\n",
    "        r=0\n",
    "        for i in range(n):\n",
    "            r=max(r,prels[i]+subls[i+1])\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "\n",
    "        pre = [0] * n\n",
    "        pre_max = [0] * (n + 1)\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        for j in range(n):\n",
    "            while prizePositions[j] - prizePositions[i] > k:\n",
    "                i += 1\n",
    "            pre[j] = j - i + 1\n",
    "            ans = max(ans, pre[j] + pre_max[i])\n",
    "            pre_max[j + 1] = max(pre_max[j], pre[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        max_after = [0] * len(prizePositions)\n",
    "        max_length = []\n",
    "        res = 0\n",
    "        for i in range(len(prizePositions)):\n",
    "            max_length.append(get_max_length(i,prizePositions,k))\n",
    "        max_after[-1] = 1\n",
    "        for i in range(len(max_after)-2,-1,-1):\n",
    "            max_after[i] = max(max_length[i] - i + 1,max_after[i+1])\n",
    "        #print(max_length)\n",
    "        #print(max_after)\n",
    "        for i in range(len(max_after)):\n",
    "            a = max_length[i] - i + 1\n",
    "            b = 0 if max_length[i] == len(max_after) - 1 else max_after[max_length[i]+1]\n",
    "            if a + b > res:\n",
    "                res = a + b\n",
    "        return res\n",
    "            \n",
    "    \n",
    "def get_max_length(i, pp, k):\n",
    "    l = i\n",
    "    r = len(pp) - 1\n",
    "    res = 1\n",
    "    t = pp[i] + k\n",
    "    while l <= r:\n",
    "        m = (l+r)//2\n",
    "        if pp[m] <= t:\n",
    "            l = m + 1\n",
    "        else:\n",
    "            r = m - 1\n",
    "    return l - 1\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        total = len(prizePositions)\n",
    "        pre_sum = [0] * total\n",
    "        suf_sum = [0] * total\n",
    "        l = 0\n",
    "        for r in range(total):\n",
    "            while l < r and prizePositions[r] - prizePositions[l] > k:\n",
    "                l += 1\n",
    "            pre_sum[r] = r-l+1\n",
    "        r = total-1\n",
    "        for l in range(total-1, -1, -1):\n",
    "            while l < r and prizePositions[r] - prizePositions[l] > k:\n",
    "                r -= 1\n",
    "            suf_sum[l] = r-l+1\n",
    "\n",
    "        ret = pre_sum[0]+suf_sum[0]-1\n",
    "        pre_max = pre_sum[0]\n",
    "        for i in range(1, total):\n",
    "            pre_max = max(pre_max, pre_sum[i-1])\n",
    "            ret = max(ret, pre_max + suf_sum[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, pos: List[int], k: int) -> int:\n",
    "        n = len(pos)\n",
    "        a = [0] * n\n",
    "        b = [0] * n\n",
    "        \n",
    "        l = r = 0\n",
    "        while r < n:\n",
    "            while pos[l] + k < pos[r]:\n",
    "                l += 1\n",
    "            a[r] = r - l + 1\n",
    "            if r:\n",
    "                a[r] = max(a[r], a[r - 1])\n",
    "            r += 1\n",
    "\n",
    "        l = r = n - 1\n",
    "        while l >= 0:\n",
    "            while pos[l] + k < pos[r]:\n",
    "                r -= 1\n",
    "            b[l] = r - l + 1\n",
    "            if l + 1 < n:\n",
    "                b[l] = max(b[l], b[l + 1])\n",
    "            l -= 1\n",
    "        \n",
    "        ans = max(a[n - 1], b[0])\n",
    "        for i in range(n - 1):\n",
    "            ans = max(ans, a[i] + b[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        total = len(prizePositions)\n",
    "        pre_sum = [0] * total\n",
    "        suf_sum = [0] * total\n",
    "        l = 0\n",
    "        for r in range(total):\n",
    "            while l < r and prizePositions[r] - prizePositions[l] > k:\n",
    "                l += 1\n",
    "            pre_sum[r] = r-l+1\n",
    "        r = total-1\n",
    "        for l in range(total-1, -1, -1):\n",
    "            while l < r and prizePositions[r] - prizePositions[l] > k:\n",
    "                r -= 1\n",
    "            suf_sum[l] = r-l+1\n",
    "\n",
    "        ret = pre_sum[0]+suf_sum[0]-1\n",
    "        pre_max = pre_sum[0]\n",
    "        for i in range(1, total):\n",
    "            pre_max = max(pre_max, pre_sum[i-1])\n",
    "            ret = max(ret, pre_max + suf_sum[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, pos: List[int], k: int) -> int:\n",
    "        n = len(pos)\n",
    "        a = [0] * n\n",
    "        b = [0] * n\n",
    "        \n",
    "        l = r = 0\n",
    "        while r < n:\n",
    "            while pos[l] + k < pos[r]:\n",
    "                l += 1\n",
    "            a[r] = r - l + 1\n",
    "            if r:\n",
    "                a[r] = max(a[r], a[r - 1])\n",
    "            r += 1\n",
    "\n",
    "        l = r = n - 1\n",
    "        while l >= 0:\n",
    "            while pos[l] + k < pos[r]:\n",
    "                r -= 1\n",
    "            b[l] = r - l + 1\n",
    "            if l + 1 < n:\n",
    "                b[l] = max(b[l], b[l + 1])\n",
    "            l -= 1\n",
    "        \n",
    "        ans = max(a[n - 1], b[0])\n",
    "        for i in range(n - 1):\n",
    "            ans = max(ans, a[i] + b[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        counter = [[0, 0] for _ in range(n)]\n",
    "        last = prizePositions[0]\n",
    "        cnt = 1\n",
    "        idx = 0\n",
    "        for x in prizePositions[1:]:\n",
    "            if x != last:\n",
    "                counter[idx][0] = last\n",
    "                counter[idx][1] = cnt\n",
    "                idx += 1\n",
    "                cnt = 1\n",
    "                last = x\n",
    "            else:\n",
    "                cnt += 1\n",
    "        counter[idx][0] = last\n",
    "        counter[idx][1] = cnt\n",
    "        idx += 1\n",
    "        if idx == 1:\n",
    "            return cnt\n",
    "        # print(counter)\n",
    "        q = deque()\n",
    "        tot = 0\n",
    "        f = [0] * (idx + 1)\n",
    "        for i in range(idx):\n",
    "            p, cnt = counter[i]\n",
    "            tot += cnt\n",
    "            while q and p - counter[q[0]][0] > k:\n",
    "                tot -= counter[q[0]][1]\n",
    "                q.popleft()\n",
    "            q.append(i)\n",
    "            f[i] = max(f[i - 1], tot)\n",
    "        # print(f[:100])\n",
    "        q = deque()\n",
    "        tot = 0\n",
    "        ret = 0\n",
    "        for i in range(idx - 1, 0, -1):\n",
    "            p, cnt = counter[i]\n",
    "            tot += cnt\n",
    "            while q and counter[q[0]][0] - p > k:\n",
    "                tot -= counter[q[0]][1]\n",
    "                q.popleft()\n",
    "            q.append(i)\n",
    "            ret = max(ret, tot + f[i - 1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "        n = len(prizePositions)\n",
    "        dic = collections.Counter()\n",
    "        l = 0\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            while l <= r and prizePositions[r] - prizePositions[l] > k:\n",
    "                l += 1 \n",
    "            res = max(res, r - l + 1 + dic[l - 1])\n",
    "            dic[r] = max(dic[r - 1], r - l + 1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: List[int], k: int) -> int:\n",
    "\n",
    "        dp = [[0] * 3 for i in range(len(prizePositions))]\n",
    "\n",
    "\n",
    "        dp[0][0] = 0\n",
    "        dp[0][1] = 1\n",
    "        dp[0][2] = 1\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i][0] = dp[i - 1][0]\n",
    "\n",
    "            idx = bisect.bisect_left(prizePositions, prizePositions[i] - k)\n",
    "\n",
    "            dp[i][1] = max(dp[i - 1][1], (dp[idx - 1][0] if idx - 1 >= 0 else 0) + i - idx + 1)\n",
    "\n",
    "            dp[i][2] = max(dp[i - 1][2], (dp[idx - 1][1] if idx - 1 >= 0 else 0) + i - idx + 1)\n",
    "\n",
    "\n",
    "        return dp[-1][2] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeWin(self, prizePositions: list[int], k: int) -> int:\n",
    "        intervals = []\n",
    "        max_beffore = []\n",
    "        start_inx = 0 \n",
    "        count = 0 \n",
    "        for inx, pos in enumerate(prizePositions):\n",
    "            count += 1\n",
    "            while pos-k > prizePositions[start_inx]:\n",
    "                count -= 1\n",
    "                start_inx += 1\n",
    "            intervals.append((count, pos))\n",
    "            if not max_beffore or max_beffore[-1][0] < count:\n",
    "                max_beffore.append((count, pos))\n",
    "\n",
    "        max_solution = 0\n",
    "        while intervals:\n",
    "            count, pos = intervals.pop()\n",
    "            while max_beffore and max_beffore[-1][1] >= pos-k:\n",
    "                max_beffore.pop()\n",
    "            candidate = count+(0 if not max_beffore else max_beffore[-1][0])\n",
    "            if candidate >= max_solution:\n",
    "                max_solution = candidate\n",
    "        return max_solution"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
